package com.dmall.play.interview.chapter09;

public class Leetcode343V1 {

    private int[] dp;

    public int integerBreak(int n) {
        dp = new int[n + 1];
        return breakInteger(n);
    }

    private int breakInteger(int n) {
        if (n == 1) {
            return 1;
        }
        if (dp[n] != 0) {
            return dp[n];
        }
        int res = -1;
        for (int i = 1; i < n; i++) {
            res = max3(res, i * (n - i), i * breakInteger(n - i));
        }
        dp[n] = res;
        return res;
    }

    private int max3(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }

    public static void main(String[] args) {
        Leetcode343V1 leetcode343 = new Leetcode343V1();
        System.out.println(leetcode343.integerBreak(10));
    }
}
